|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
|
|
| |
|
|
Abstraction in Automata Algorithms
Kocourek, Tomáš ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Tato práce si klade za cíl implementaci a experimentální porovnání protiřetězcových algoritmů s abstrakcí a bez abstrakce, které testují prázdnost alternujících automatů. Autor také navrhuje vlastní algoritmy s abstrakcí a navrhuje několik optimalizací pro existující abstraktní algoritmy. Práce popisuje teoretické pozadí studovaných algoritmů a navrhuje efektivní způsob implementace datových struktur, které jsou těmito algoritmy používány. Experimentální vyhodnocení na náhodných automatech ukazuje, že algoritmy bez abstrakce vykazují obecně lepší výsledky, neboť nevyužívají náročné operace průniku a komplementace shora a zdola uzavřených množin. V případě automatů s vysokou hustotou přechodů však algoritmy bez abstrakce zpomalují a algoritmy s abstrakcí naopak zrychlují.
|
|
|
Algorithm for word morphisms fixed points
Matocha, Vojtěch ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In the present work we study the first polynomial algorithm, which tests if the given word is a fixed point of a nontrivial morphism. This work contains an improved worst-case complexity estimate O(m · n) where n denotes the word length and m denotes the size of the alphabet. In the second part of this work we study the union-find problem, which is the crucial part of the described algorithm, and the Ackermann function, which is closely linked to the union-find complexity. We summarize several common methods and their time complexity proofs. We also present a solution for a special case of the union-find problem which appears in the studied algorithm. The rest of the work focuses on a Java implementation, whose time tests correspond to improved upper bound, and a visualization useful for particular entries.
|
|
|
Arithmetical completeness of the logic R
Holík, Lukáš ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
The aim of this work is to use contemporary notation to build theory of Rosser logic, explain in detail its relation to Peano arithmetic, show its Kripke semantics and finally using plural self-reference show the proof of arithmetical completeness. In the last chapter we show some of the properties of Rosser sentences. Powered by TCPDF (www.tcpdf.org)
|
|
|
Commuting continuous functions without a common fixed point
Karasová, Klára ; Vejnar, Benjamin (advisor) ; Cúth, Marek (referee)
The topic of the thesis are common fixed points of commuting functions. With the help of the Mountain climbing theorem we will prove the theorem about extending commuting functions, which will allow us to construct commuting self-mappings of the unit interval with no common fixed point. For the next part we prove several versions of the extending commuting functions theorem using different versions of the Mountain climbing theorem. We will also prove that if X is a dendroid, S an abelian semigroup of continuous monotone self-mappings of X and f : X → X commutes with each element of S, then f and S have a common fixed point. 1
|
|
|
Fixed point theorems in the theory of differential equations
Zelina, Michael ; Pražák, Dalibor (advisor) ; Bárta, Tomáš (referee)
This thesis is devoted to show various applications of fixed point theorems on dif- ferential equations. In the beginning we use a notion of topological degree to derive several fixed points theorems, primarily Brouwer, Schauder and Kakutani-Ky Fan the- orem. Then we apply them on a wide range of relatively simple problems from ordinary and partial differential equations (ode and pde). Finally, we take a look on a few more complex problems. First is an existence of a solution to the model of mechanical os- cillator with non-monotone dependence of both displacement and velocity. Second is a solution to so called Gause predator-prey model with a refuge. The last one is cer- tain partial differential equation with a constraint which determines maximal monotone graph. 1
|
|
|
Linear version of Holub's algorithm
Tvrdý, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a step-by-step visualization for particular input words. 1
|
|
|
Arithmetical completeness of the logic R
Holík, Lukáš ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
The aim of this work is to use contemporary notation to build theory of Rosser logic, explain in detail its relation to Peano arithmetic, show its Kripke semantics and finally using plural self-reference show the proof of arithmetical completeness. In the last chapter we show some of the properties of Rosser sentences. Powered by TCPDF (www.tcpdf.org)
|
|
|
Analysis of the CubeHash proposal
Stankovianska, Veronika ; Tůma, Jiří (advisor) ; Hojsík, Michal (referee)
The present thesis analyses the proposal of CubeHash with spe- cial emphasis on the following papers: "Inside the Hypercube" [1], "Sym- metric States and Their Improved Structure" [7] and "Linearisation Frame- work for Collision Attacks" [6]. The CubeHash algorithm is presented in a concise manner together with a proof that the CubeHash round function R : ({0, 1}32 )32 → ({0, 1}32 )32 is a permutation. The results of [1] and [7] con- cerning the CubeHash symmetric states are reviewed, corrected and substan- tiated by proofs. More precisely, working with a definition of D-symmetric state, based on [7], the thesis proves both that for V = Z4 2 and its linear subspace D, there are 22 |V | |D| D-symmetric states and an internal state x is D-symmetric if and only if the state R(x) is D-symmetric. In response to [1], the thesis presents a step-by-step computation of a lower bound for the num- ber of distinct symmetric states, explains why the improved preimage attack does not work as stated and gives a mathematical background for a search for fixed points in R. The thesis further points out that the linearisation method from [6] fails to consider the equation (A ⊕ α) + β = (A + β) ⊕ α (∗), present during the CubeHash iteration phase. Necessary and sufficient conditions for A being a solution to (∗) are...
|
guest ::
